package com.qisi.kandroidshalon.leetcode;

import android.util.Log;

import java.util.LinkedList;
import java.util.List;

public class GrayCode {
    private static final String TAG = "GrayCode";

    /**
     * 89:
     * n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
     * 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
     * 第一个整数是 0
     * 一个整数在序列中出现 不超过一次
     * 每对 相邻 整数的二进制表示 恰好一位不同 ，且
     * 第一个 和 最后一个 整数的二进制表示 恰好一位不同
     * 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
     * <p>
     * 思路: 遇到构造序列问题，从最简单的开始往后迭代，找出规律
     * n = 1  000 - 001
     * n = 2  000 - 001 - 011 - 010 (后半部分是f(1)结果的反转+2^1)
     * n = 3  000 - 001 - 011 - 010 - 110 - 111 - 101 - 100  (后半部分是f(2)结果的反转+2^2)
     * ...
     * n = n 长度2^n, 后半段是f(n-1)的反转+2^(n-1)
     * <p>
     * 另外取巧的方法是采用公式:i^(i>>1)
     */

    public static List<Integer> grayCode(int n) {
        if (n == 1) {
            List<Integer> res = new LinkedList<>();
            res.add(0);
            res.add(1);
            return res;
        }
        //f(n-1)
        List<Integer> last = grayCode(n - 1);
        //后半段
        List<Integer> half = new LinkedList<>();
        for (int i = last.size() - 1; i >= 0; i--) {
            half.add(last.get(i) + (1 << (n - 1)));
        }
        last.addAll(half);
        Util.dumpList(last);
        return last;
    }
}
